% Exemplo de relatório técnico do IC
% Criado por P.J.de Rezende antes do Alvorecer da História.
% Modificado em 97-06-15 e 01-02-26 por J.Stolfi.
% Last edited on 2003-06-07 21:12:18 by stolfi

% modificado em 1o. de outubro de 2008

\documentclass[11pt,twoside]{article}

\usepackage{epsf}
\usepackage{graphicx}
\usepackage{techrep-ic}
\usepackage{amsthm}
\usepackage{cite}
\usepackage{float}

%%% SE USAR INGLÊS, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A SEGUIR:
\usepackage[brazil]{babel}
%% \usepackage[english]{babel}

%%% SE USAR CODIFICAÇÃO LATIN1, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A
%%% SEGUIR:
%% \usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

\usepackage{color}
\usepackage{listings}
\lstset{ %
backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
basicstyle=\ttfamily\small,
numberstyle=\small,
keywordstyle=\color{black}\bfseries,
language=Java,                % choose the language of the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=4,              % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,        % sets automatic line breaking
breakatwhitespace=false,    % sets if automatic breaks should only happen at whitespace
columns=fullflexible,
escapeinside={\%}{)}          % if you want to add a comment within your code
}

\lstnewenvironment{shell}
	{\lstset{language=csh, frame=single}}
	{}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% Número do relatório

\TRNumber{02}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{10}  % Dois dígitos apenas
\TRMonth{05} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{G. S. de Paula \and P. R. Costa \and R. Dominiquini}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{Sub-Projeto 3:\\Banco}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% O que segue é apenas uma sugestão - sinta-se à vontade para
% usar seu formato predileto, desde que as margens tenham pelo
% menos 25mm nos quatro lados, e o tamanho do fonte seja pelo menos
% 11pt. Certifique-se também de que o título e lista de autores
% estão reproduzidos na íntegra na página 1, a primeira depois da
% página de capa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{De Paula, Costa e Dominiquini}{Banco}
\pagestyle{myheadings}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TÍTULO e NOMES DOS AUTORES, completos, para a página 1.
% Use "\\" para quebrar linhas, "\and" para separar autores.
%
\title{Sub-Projeto 3: Banco}

\author{
Gustavo de Paula\thanks{Instituto  de Computação, Universidade
Estadual  de Campinas, 13081-970  Campinas,  SP.}  \and
Paulo de Almeida Costa\footnotemark[1] \and
Rafael Baboni Dominiquini\footnotemark[1]}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract} 

Neste relatório descrevemos o subprojeto 3, neste projeto recebemos a implementação de um banco, com operações de depósito, saque e saldo, e conectamos este módulo ao módulo de transporte utilizando um componente de middleware. Com este acoplamento imitamos o funcionamento de um sistema bancário distribuído, com operações sendo enviadas para as diversas réplicas e executadas em cada uma delas. Na etapa atual espera-se que o sistema fique inconsistente pois é possível que haja a perda de mensagens e troca de ordem das operações. Nos próximos subprojetos esperamos adicionar funcionalidades ao middleware de modo que a consistência do sistema seja garantida.

\end{abstract}

\section{Introdução}

Foi disponibilizado no repositório da disciplina uma implementação simples de um banco, este possui operações de depósito, saque e saldo. Nossa tarefa foi acoplar este banco ao componente de transporte para possibilitar o funcionamento distribuído do banco com diversas réplicas. Em nosso projeto escolhemos por fazer o acoplamento inserindo um middleware entre o banco e a camada de transporte. Este middleware é responsável por toda a comunicação entre as diversas réplicas abstraindo todos os detalhes da aplicação distribuída, para o banco a interface utilizada fornece métodos para enviar uma operação para as réplicas e obter uma operação da fila para execução.

Nesta atividade inicial o middleware não garante a consistência do sistema distribuído, as operações são enfileiradas no recebimento e enviadas para execução na ordem em que foram recebidas por cada réplica, por conta da falta de ordenação total do multicast ethernet esta ordem varia em cada réplica. No fim temos diferentes réplicas nas quais o saldo final das contas geralmente difere. A ordenação total das operações e consistência do sistema será obtida com a adição do algoritmo de Herman-Verjus~\cite{herman79} ao middleware.

Realizamos, em sua maioria, adições às classes fornecidas para interligar o banco ao middleware, o funcionamento das operações de contas foi mantido o mesmo. O banco possui dois modos de operações, o automático e o normal. O automático corresponde a uma série de operações aleatórias e o normal fornece um terminal ao usuário simulando um caixa automático. A adição que criar um sistema de replicação em que cada operação é enviada e executada em todas as réplicas.

Fizemos uma série de testes para validar o programa, mostrar a falta de ordenação total das operações e diferença no estado final das réplicas. Estes testes foram executados no cluster do LSD. Algumas modificações no código do banco automático foram feitas para facilitar os testes, sendo a principal delas a adição de um mecanismo de controle para que as réplicas fiquem sabendo sobre o início e fim da operação de cada uma delas, isto foi feito para evitar que réplicas entrem em funcionamento antes das outras e muitas mensagens sejam perdidas, o que atrapalharia a avaliação dos resultados do teste.

\section{Implementação}

A classe \emph{Bank}, além de disponibilizar uma interface com o usuário, contém um conjunto de contas do tipo BankAccount, com informações de identificação da conta e saldo. Esta última implementa as operações básicas de saque e depósito. O terminal Bank espera o usuário selecionar uma operação sobre uma conta e a envia utilizando um objeto do tipo BankOperation através do middleware. O envio da operação é feito pelo método \emph{setOp}. Na nossa versão a operação não é executada no momento em que o usuário a requer, a execução das operações é assíncrona.

O middleware possui uma fila de operações para cada conta. Ao receber uma nova operação pelo transporte ela é adicionada à fila para a conta específica. Este recebimento também é assíncrono e executado em uma outra thread. Ao receber uma operação por \emph{setOp}, o middleware envia a mensagem por multicast aos outros processos utilizando o transporte e enfileira a operação. O método \emph{getOp} retorna a primeira operação da fila quando requisitado pelo banco. O recebimento de operações é feito por uma thread ativa. O uso de filas separadas para cada conta permite um maior desempenho da aplicação, já que duas operações em contas diferentes, por definição, não são concorrentes e podem ser executadas simultaneamente. Um semáforo foi utilizado para evitar que duas operações sobre a mesma conta ocorram concorrentemente.

Completando o fluxo de trabalho do banco, incluímos uma thread para execução de operações. Esta thread possui interligação com o middleware no sentido de que a cada iteração ela requisita uma nova operação e a executa sobre a conta especifícada. Cada operação é executada em uma nova thread, permitindo que operações sobre contas diferentes ocorram ao mesmo tempo.

Maiores detalhes da implementação podem ser vistos na documentação Javadoc do código. Ela contém descrições dos métodos e atributos de cada classe implementada.

\section{Testes}

Para verificar a ausência de ordenação total das operações trocadas pela camada de transporte fizemos um teste simples utilizando o cluster do LSD. Neste teste instanciamos a partir do nó mestre via \emph{ssh} uma réplica em cada um dos nós (n02, n03, n04 e n05). Cada réplica executou o banco automático e gravamos um log contendo todas as operações efetuadas e o balanço final das contas. Como a área é compartilhada temos, no final, um log para cada réplica e executando \emph{diff} conseguimos notar as trocas de ordem entre as mensagens.

Para automatizar o teste criamos um script que compila o programa e executa o processo em cada nó utilizando ssh. Para automatizar a conexão de ssh tivemos que fazer a configuração de chaves RSA nos hosts. Como mencionado anteriormente, alteramos o middleware para incluir um mecanismo de controle da execução das réplicas fazendo com que as réplicas possam saber o estado uma das outras. Trocamos mensagens de estado no início e final da execução do auto bank e assim podemos sincronizar a execução para iniciar quando todas as réplicas estiverem de pé e parar apenas quando todas tiverem parado. Isto evita a perda de mensagens no início e fim da execução de cada réplica.

\section{Resultados}

Observando o resultado dos testes através dos logs observamos um número razoável na troca de mensagens e balanço de algumas contas. Abaixo mostramos o saldo final das contas em cada uma das quatro réplicas:

\begin{center}
\begin{tabular}{| c || c | c | c | c |}
  \hline			
  \textbf{Réplica} & \textbf{Conta 1} & \textbf{Conta 2} & \textbf{Conta 3} & \textbf{Conta 4} \\ \hline \hline
  \textbf{1} & 12053 & 72302 & 17065 & 12583 \\ \hline
  \textbf{2} & 12053 & 71936 & 17065 & 12559 \\ \hline
  \textbf{3} & 11943 & 71895 & 16617 & 12583 \\ \hline
  \textbf{4} & 12053 & 71936 & 17065 & 12583 \\ 
  \hline  
\end{tabular}
\end{center}

O número de trocas de operações, de um total de 6081 mensagens trocadas, foi obtido utilizando o script \emph{diff\_lines} o resultado está a seguir:

\begin{center}
\begin{tabular}{| c || c | c | c | c |}
  \hline			
    & 1 & 2 & 3 & 4 \\ \hline \hline
  1 & -- & 174 & 174 & 139 \\ \hline
  2 & 174 & -- & 189 & 152 \\ \hline
  3 & 174 & 189 & -- & 156 \\ \hline
  4 & 139 & 152 & 156 & -- \\ \hline
  \hline  
\end{tabular}
\end{center}

Contando as linhas dos logs vemos que o número de linhas é idêntico, portanto, nenhuma operação foi perdida, o que houve foi apenas a troca de ordem entre elas. Os resultados mostram que a troca de ordem foi totalmente aleatória. Podemos explicar isto pelo fato de que tempo de transmissão entre os nós varia com o tempo e mensagens enviadas por um nó acabam chegando em tempos diferentes em cada um dos outros nós possibilitando a troca de ordem. O modo como é feita a ordenação das mensagens no middleware contribui para a inconsistência, já que elas são ordenadas pelo tempo de chegada na réplica de destino, ignorando a ordenação natural das mensagens.

Seria possível, em um sistema sincronizado por NTP, obter muito menos trocas de mensagens se ordenássemos a fila pelo timestamp de envio da mesma, como a dessincronia entre as diversas réplicas é baixa, o timestamp de envio acaba servindo como uma boa aproximação para a ordenação total.

\section{Conclusão}

Conseguimos cumprir o objetivo do projeto que era o de acoplar o banco à camada de transporte, criando assim um sistema bancário replicado. O principal artefato gerado nesta etapa foi o middleware, o qual será incrementado nas próximas etapas para tornar o sistema distribuído consistente através da implementação do algoritmo de Herman-Verjus. A arquitetura desenvolvida desta maneira, com o uso do middleware, facilita a extensão e adição de novas funcionalidades ao projeto, o que será de grande valia nas etapas posteriores.

Através de testes conseguimos comprovar que a operação do banco, na versão atual, não é consistente. Através de um teste com quatro réplicas e quatro contas observamos divergências nos balanços das contas nas diversas réplicas. O objetivo das etapas posteriores é o de eliminar estas divergências através da aplicação de um algoritmo que gere uma ordenação total das operações, fazendo com que as réplicas executem as operações na mesma ordem, mantendo o estado do sistema consistente ao fim de todas as operações executadas.

\begin{thebibliography}{1}

\bibitem{herman79}
D.~Herman and J.~P. Verius.
\newblock An algorithm for maintaining the consistency of multiple copies.
\newblock In {\em Proceedings of the 1st International Conference on
  Distributed Computing Systems}, pages 625--631, Washington, DC, 1979. IEEE
  Computer Society.

\end{thebibliography}

\end{document}
